#pragma once

#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

#define BinNodePosi(T) BinNode<T>*
#define stature(p) ( (p) ? (p)->height : -1 )
typedef enum { RB_RED, RB_BLACK } RBColor;

template <typename T>
struct BinNode
{
  T data;
  BinNodePosi(T) parent; BinNodePosi(T) lc; BinNodePosi(T) rc;
  int height;
  int npl;
  RBColor color;
  BinNode() : parent(nullptr) {}
  BinNode(T e, BinNodePosi(T) p = NULL, BinNodePosi(T) lc = NULL, BinNodePosi(T) rc = NULL, int h = 0, int l = 1, RBColor c = RB_RED) :
    data(e), parent(p), lc(lc), rc(rc), height(h), npl(l), color(c) { }

  int size();
  BinNodePosi(T) insertAsLC(T const& e);
  BinNodePosi(T) insertAsRC(T const& e);
  BinNodePosi(T) succ();
  template<typename VST> void travLevel(VST&);
  template<typename VST> void travPre(VST&);
  template<typename VST> void travIn(VST&);
  template<typename VST> void travPost(VST&);

  bool operator < (BinNode const& bn) { return data < bn.data; }
  bool operator == (BinNode const& bn) { return data == bn.data; }
};

#define IsRoot(x) ( !((x).parent) )
#define IsLChild(x) ( ! IsRoot(x) && ( &(x) == (x).parent->lc) )
#define IsRChild(x) ( ! IsRoot(x) && ( &(x) == (x).parent->rc) )
#define HasParent(x) ( ! IsRoot(x) )
#define HasLChild(x) ( (x).lc )
#define HasRChild(x) ( (x).rc )
#define HasChild(x) (  HasLChild(x) || HasRChild(x) )
#define HasBothChild(x) (  HasLChild(x) && HasRChild(x) )
#define IsLeaf(x) ( ! HasChild(x) )
#define Sibling(x) ( IsLChild( *(x) ) ? (x)->parent->rc : (x)->parent->lc )
#define Uncle(x) ( IsLChild(*((x)->parent ))  ? (x)->parent->parent->rc : (x)->parent->parent->lc )
#define FromParentTo(x) ( IsRoot(x) ? _root : ( IsLChild(x) ? (x).parent->lc : (x).parent->rc ) )

template <typename T>
static void release(BinNodePosi(T) x) {
}

template <typename T>
static void release(T const& x) {
}

template <typename T>
static int removeAt(BinNodePosi(T) x) {
  if (!x) return 0;
  int n = 1 + removeAt(x->lc) + removeAt(x->rc);
  release(x->data); release(x); return n;
}

template<typename T>
class BinTree
{
protected:
  int _size;
  BinNodePosi(T) _root;
  std::queue<T> s;
  virtual int updateHeight(BinNodePosi(T) x);
  void updateHeightAndAbove(BinNodePosi(T) x);

public:
  BinTree() : _size(0), _root(nullptr) {  }
  template<typename iter>
  BinNodePosi(T) buildTreeFromPreAndIn(iter pre_first, iter pre_last, iter in_first, iter in_last);
  template<typename iter>
  BinNodePosi(T) buildTreeFromInAndPost(iter pre_first, iter pre_last, iter in_first, iter in_last);

  BinNodePosi(T) preAndInOrderCreate(std::vector<T> pre, std::vector<T> in);
  BinNodePosi(T) inAndPostOrderCreate(std::vector<T> in, std::vector<T> post);
  ~BinTree() { if (0 < _size) remove(_root); }
  int size() const { return _size; }
  bool empty() const { return !_root; }
  BinNodePosi(T) root() const { return _root; }
  BinNodePosi(T) insertAsRoot(T const& e);
  BinNodePosi(T) insertAsLC(BinNodePosi(T) x, T const& e);
  BinNodePosi(T) insertAsRC(BinNodePosi(T) x, T const& e);
  BinNodePosi(T) attachAsLC(BinNodePosi(T) x, BinTree<T>*& t);
  BinNodePosi(T) attachAsRC(BinNodePosi(T) x, BinTree<T>*& t);
  int remove(BinNodePosi(T) x);
  void release(BinNodePosi(T) x);
  void release(T const& x);
  BinTree<T>* secede(BinNodePosi(T) x);
  template <typename VST>
  void travLevel(VST& visit) { if (_root) _root->travLevel(visit); }
  template <typename VST>
  void travPre(VST& visit) { if (_root) _root->travPre(visit); }
  template <typename VST>
  void travIn(VST& visit) { if (_root) _root->travIn(visit); }
  template <typename VST>
  void travPost(VST& visit) { if (_root) _root->travPost(visit); }
  bool operator < (BinTree<T> const& t) { return _root && t._root && std::less<T>{ }(_root, t._root); }
  bool operator ==(BinTree<T> const& t) { return _root && t._root && (_root == t._root); }
};

#include "bintree-impl.hpp"